/**
 * 给定一个二叉树，判断它是否是
 * 平衡二叉树
 *方法一: 时间复杂度: O(N)
 */

//这个方法的时间复杂度为O(N^2)
class Solution {
    public boolean isBalanced(TreeNode root) {
        //如果当前节点为空节点,则以root为根节点的二叉树一定平衡
        if(root == null){
            return true;
        }
        //当前节点的左子树的高度
        int lefth = getHeight(root.left);
        //当前节点的右子树的高度
        int righth = getHeight(root.right);
        //左右子树的高度差,高度差大于1说明以root为根节点的二叉树不平衡
        if(Math.abs(lefth - righth) > 1){
            return false;
        }
        //只有以root为根节点的左右子树均为平衡二叉树才说明以root为根节点的二叉树为平衡二叉树
        return isBalanced(root.left) && isBalanced(root.right);
    }
    //求二叉树的高度
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.max(leftHeight,rightHeight) + 1;
    }
}

